"""
1792. 最大平均通过率
中等
相关标签
premium lock icon
相关企业
提示
一所学校里有一些班级，每个班级里有一些学生，现在每个班都会进行一场期末考试。给你一个二维数组 classes ，其中 classes[i] = [passi, totali] ，表示你提前知道了第 i 个班级总共有 totali 个学生，其中只有 passi 个学生可以通过考试。

给你一个整数 extraStudents ，表示额外有 extraStudents 个聪明的学生，他们 一定 能通过任何班级的期末考。你需要给这 extraStudents 个学生每人都安排一个班级，使得 所有 班级的 平均 通过率 最大 。

一个班级的 通过率 等于这个班级通过考试的学生人数除以这个班级的总人数。平均通过率 是所有班级的通过率之和除以班级数目。

请你返回在安排这 extraStudents 个学生去对应班级后的 最大 平均通过率。与标准答案误差范围在 10-5 以内的结果都会视为正确结果。



示例 1：

输入：classes = [[1,2],[3,5],[2,2]], extraStudents = 2
输出：0.78333
解释：你可以将额外的两个学生都安排到第一个班级，平均通过率为 (3/4 + 3/5 + 2/2) / 3 = 0.78333 。
示例 2：

输入：classes = [[2,4],[3,9],[4,5],[2,10]], extraStudents = 4
输出：0.53485


提示：

1 <= classes.length <= 105
classes[i].length == 2
1 <= passi <= totali <= 105
1 <= extraStudents <= 105
"""
import heapq
from typing import List


class Solution:
    def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:
        """
        最小堆
        :param classes:
        :param extraStudents:
        :return:
        """
        h = []
        def diffRate(success:int,total:int) -> float:
            return (success+1)/(total+1) - success/total

        for i in classes:
            #用负数是默认heapq是最小堆，但是我们要取最大值。重要：可把数据存到元组种，只要要比较的值放在第一位即可，python会根据顺序冲前往后排序
            heapq.heappush(h,(-diffRate(i[0],i[1]),i[0],i[1]))

        for i in range(extraStudents):
            #每次取最优的
            _,s,t = heapq.heappop(h)
            heapq.heappush(h,(-diffRate(s+1,t+1),s+1,t+1))

        #结果
        ans = 0
        for _,s,t in h:
            ans += s/t
        return ans/(len(classes))

if __name__ == '__main__':
    print(Solution().maxAverageRatio([[1,2],[3,5],[2,2]],2))
    print(Solution().maxAverageRatio([[2,4],[3,9],[4,5],[2,10]],4))

    my_list = ["1", "2", "3"]
    remove = my_list.pop()
    print(remove)  # ['1', '3']
    print(my_list)  # ['1', '3']